704.二分查找

题目链接: 二分查找

思路：比较数组中间位置的值nums[middle]和目标值target的大小，从而确定查找的左右区间
个人习惯用左闭右闭的形式[left，right]，循环条件是left <= right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int middle = left + (right - left) / 2;
            if(target > nums[middle]){
                left = middle + 1;
            }
            if(target < nums[middle]){
                right = middle - 1;
            }
            if(target == nums[middle]){
                return middle;
            }
        }
        return -1;
    }
}

27.移除元素

题目链接: 移除元素

方法一：快慢指针
遍历快指针fastIndex，若不是移除元素，慢指针slowIndex跟着一起移动，并复制到新数组元素；
如果碰到要移除的元素值，则slowIndex不变即可

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeElement(int[] nums, int val) {
        int slowIndex = 0;
        for(int fastIndex = 0; fastIndex < nums.length; fastIndex++){
            if(nums[fastIndex] != val){
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

方法二：相向指针法
左指针开始遍历，循环条件是left <= right
右指针控制长度；当左指针碰到移除元素时，把右指针元素放到左指针位置上，并且右指针左移，减小长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        //将right移到从右数第一个值不为val的位置
        while(right >= 0 && nums[right] == val){
            right--;
        }
        while(left <= right){
            if(nums[left] == val){
                nums[left] = nums[right];
                right--;
            }
            left++;
            //若遍历过程中，再次出现连续几个val，则也需要将right移到不为val的位置
            while(right >= 0 && nums[right] == val){
                right--;
            }
        }
        return left;
    }
}